#!/usr/bin/env perl

# drawsome dictionary generator 0.1 - turns dictionary files into json tree
# dict = [[char0, [payload0], [[char1, [payload1], [[char2, ...]]]]]]
# payload is [word, coins]

use strict;
use JSON::XS;

print encode_json(process_input());

sub process_input {
	my $dict = [];

	while(<>){
		chomp;
		my($word, $coins) = split ',' or next;
		$word = uc $word;
		process_word($dict, join('', sort {$a cmp $b} split '', $word), $word, int $coins, 0);
	}

	return $dict;
}

sub process_word {
	my($dict, $word_asc, $word, $coins, $pos) = @_;

	my $char      = substr $word_asc, $pos,     1;
	my $char_next = substr $word_asc, $pos + 1, 1;

	my $i = bin_search($dict, $char);
	if(defined $dict->[$i]){
		if($char_next){
			process_word($dict->[$i][2] ||= [], $word_asc, $word, $coins, $pos + 1);
		}
		else{
			$dict->[$i][1][bin_search($dict->[$i][1], $word)] = [$word, $coins];
		}
	}
	else{
		if($char_next){
			my $dict_next = [];
			$dict->[$i] = [$char, [], $dict_next];
			process_word($dict_next, $word_asc, $word, $coins, $pos + 1);
		}
		else{
			$dict->[$i] = [$char, [[$word, $coins]]];
		}
	}
}

# from wikipedia :x
sub bin_search {
	my($arr, $str) = @_;
	return 0 unless @$arr;

	my $min = 1;
	my $mid;
	my $max = @$arr;

	my $cmp;
	do{
		$mid = int(($min + $max) / 2);
		$cmp = $str cmp $arr->[$mid - 1][0];
		if(!$cmp){
			$mid--;
			$min = $max + 1; # last
		}
		elsif($cmp > 0){
			$min = $mid + 1;
		}
		else{
			$max = $mid - 1;
		}
	} until $min > $max;

	# XXX adjust array if no match
	if($cmp){
		$mid-- if $cmp < 0;
		splice @$arr, $mid, 0, undef;
	}

	return $mid;
}
